This application relates in general to a memory controller for a multiprocessor computer system, and in specific to a mechanism for maximizing available bandwidth on the address bus by utilizing and xe2x80x9csnapshotxe2x80x9d matrix to reduce xe2x80x9cretriesxe2x80x9d of conflicting memory data requests.
The different processors of the multiprocessor network typically share access with a common memory, such as a shared RAM memory, that pulls a cache line of data and sends it to a processor, which then puts the line into its cache. Requests for access to the shared memory from the given processors are routed through a memory controller. This prevents concurrent accesses to the same data, and as such, a requesting processor will receive current data and not stale data from memory. The memory controller receives a read request from one of the processors. The memory controller then reads the data from the memory. The memory controller then formats a response to the request that includes the data, and then sends the response back to the requesting processor.
In doing so, the memory controller has to make sure that it has not violated coherency issues which might occur incases where, in a first instance, there is a read to a cache line and later there is another read to the same cache line from a different processor before the data for the first read was returned by the memory controller. In such situations, the memory controller has to make sure that in processing the second read it does not violate coherency by sending the old data which it has in the memory to the second read. The data that the controller returns for the first read could be modified by the processor which got the first read response. Instead, with respect to the second read, the memory controller needs to make sure that the data for the second read is from the processor that originated the first read. This problem has been solved by performing a retry operation. Accordingly, the memory controller will issue a xe2x80x9cretry signal,xe2x80x9d which essentially tells the microprocessor which is sending the second read request to retry the read request at a later time. Consequently, the effect of the memory controller not being ready to return the response for the data and the subsequent retry operations, is that more of the system bus bandwidth is used. Thus, the prior art retry operations does lower the system performance, because the operations will generate unnecessary transactions on the system bus.
Furthermore, prior art memory controllers are designed to process requests in order, thus the memory controllers would return a response with the requested data in the same order that the requests for data are received. Some memory controllers also issue read requests to memory in the same order as the corresponding requests are received by the memory controller. Hence, the returns from the memory are also in the same order, causing the request transactions to be always completed in the order in which they were received. The next transaction that will be available to be returned to a processor is clearly known, since the memory controller operates according to the received order of the requests. Consequently, the memory controller can perform preparation operations in anticipation of returning the data from memory. However, the order requirements of the prior art controllers have several limitations. Servicing the requests in order requires a large amount of queue space. Data received by the memory controller from the memory must be held until the request associated with the data is sequentially the current request. Thus, the data from memory must be queued. This also causes a back log of requests, as requests cannot be satisfied until their associated data is returned. As a further consequence, the prior art controllers experience long latencies, because of the queuing of the requests and the data. Also, since the requests must be processed in a particular order, the requests cannot be re-ordered by the controller to maximize bus utilization and throughput. Thus, if address 1 is followed by address 2 and then address 3, the data supplied must be in phase accordingly (i.e. data 1, data 2, data 3, etc.) As such, the hardware of the system is inefficiently used.
Therefore, there is a need in the art for a memory controller that more efficiently uses queue spaces by permitting out of order returns and avoids the bandwidth intensive xe2x80x9cretryxe2x80x9d scheme so as to optimize use of the memory bus. The hardware design should be simple and efficient, so that high frequency operation is possible. The design should be simple to understand, so that it is easy to verify.
These and other objects, features and technical advantages are achieved by a system and method that permits the aforementioned inefficiencies to be ameliorated by maximizing the available bandwidth through a mechanism which uses a xe2x80x9csnapshotxe2x80x9d matrix.
The invention is a memory controller that is connected between at least one bus and a memory, with the bus connected to at least two processors. Note the inventive memory controller can operate with a single processor, however, the advantages of the invention are realized when the bus has at least two processors. The inventive memory controller manages read requests from the processors. The memory controller fetches the data from memory and checks to see if another processor has ownership of the requested data. If so, the owning processor will respond to the requesting processor. The invention, after receiving a read request, examines on-chip resources to determine whether prior requests are pending that involve the same memory resources as the received read request, e.g a cache line of memory in RAM. The invention uses a snapshot matrix to track received transactions conflicting with the prior pending transactions. Each received transaction is assigned a unique identification, based on a maximum number of transactions the invention can manage at a certain time. The prior pending transactions are reviewed in order to determine whether any conflicts exist with the received transaction. In the event of a conflict, the received transaction is entered into a snapshot matrix. All prior conflicting transactions must be processed before data is returned for the received transaction. Note that multiple read requests may be processed out of order to maximize the memory bus utilization and throughput. Note that the completed transaction may be returned in an order that is different from the read request order. Since transactions are processed out of order, data return latency is reduced. The snapshot matrix imposes strict ordering between conflicting transactions.
Therefore, it is a technical advantage of the present invention to have a memory controller provides coherency between data requests and data returns for read request transactions, and thereby improve system performance.
It is another technical advantage of the present invention that requests can originate from multiple processors located on multiple buses.
It is a further technical advantage of the present invention that the memory controller may be implemented in hardware such that the invention can operate at high frequencies and the logic can be easily verified.
It is a still further technical advantage of the present invention that the memory controller can maximize available bandwidth on the address bus.
It is a still further technical advantage of the present invention to use a bitmap to record pending transactions such that after a pending transaction has been completed, a clear signal will be generated to clear all future transactions that are waiting for the now completed transaction to finish.
The present invention avoids retrying requests that are conflicting with already pending requests. Pending requests are requests for which the memory data has not yet been returned. If a conflicting request is retried, the request will be reissued by the processor. This wastes precious system bus address bandwidth.
Every transaction is assigned a unique identifier as soon as it is received. When a conflicting request is discovered, it is entered into a xe2x80x9csnapshotxe2x80x9d matrix. Ideally, the snapshot natrix contains only the transaction identifiers which are conflicting with the received request. But, for simplicity, all the previous transactions could be copied into the snapshot matrix. The idea is that a conflicting transaction should be completed only after all the previous transactions conflicting with the new transaction are completed.
When all the previously conflicting transactions are completed, the memory controller will issue a request on the system bus to recall the data for the transaction that was initially inserted into the snapshot matrix. If any processor has the data associated with this transaction, the data will be supplied by the processor. This data will be returned as response for transaction that was entered into the snapshot. If none of the processors had modified the data, the data from the memory will be returned as the response.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.